#include <cstdio>

int extgcd( int a, int b, int &x, int &y )
{
    if ( b == 0 ) { x = 1; y = 0; return a; }
    int d = extgcd( b, a % b, x, y );
    int t = x; x = y; y = t - a / b * y;
}

int gcd( int a, int b )
{
    int rem;
    while ( b )
    {
        rem = a % b;
        a = b;
        b = rem;
    }
    return a;
}

long long pow( long long p, int n )
{
    long long ans = 1;
    int pos = 1;
    while ( pos <= n ) pos <<= 1;
    pos >>= 1;
    while ( pos )
    {
        ans = ans * ans % 1000000007;
        if ( pos & n ) ans = ans * p % 1000000007;
        pos >>= 1;
    }
    return ans;
}

int main( )
{
    int t, cas = 1, n, m, i, x, y;
    long long ans;
    scanf("%d", &t);
    while ( t-- )
    {
        scanf("%d%d", &n, &m);
        ans = 0;
        for ( i = 0; i < m; i++ )
            ans = ( ans + pow( n, gcd( m, i ) ) ) % 1000000007;
        if ( m & 1 )
            ans = ( ans + m * pow( n, m / 2 + 1 ) % 1000000007 ) % 1000000007;
        else
            ans = ( ( ans + m / 2 * pow( n, m / 2 + 1 ) % 1000000007 ) % 1000000007 + m / 2 * pow( n, m / 2 ) % 1000000007 ) % 1000000007;
        extgcd( m * 2, 1000000007, x, y );
        x = ( x + 1000000007 ) % 1000000007;
        ans = ans * x % 1000000007;
        printf("Case #%d: %I64d\n", cas++, ans);
    }
    return 0;
}
